#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
	return x*f;
}
int n,m,k,r,s[N],t[N],u[N],v[N];

vector<pair<int,int> > e[N]; 

int d[N];
int dis(int s,int t){
	for(int i=1;i<=n;i++) d[i]=1e9;
	queue<int> q;
	d[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(pair<int,int> pl:e[u]){
			int v=pl.first,w=pl.second;
			if(d[v]>d[u]+w) d[v]=d[u]+w,q.push(v);
		}
	}
	return d[t];
}

signed main(){
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	n=read(),m=read(),k=read(),r=read();
	for(int i=1;i<=m;i++) u[i]=read(),v[i]=read();
	for(int i=1;i<=k;i++) s[i]=read(),t[i]=read();
	int ans=0;
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			for(int p=1;p<=n;p++) e[p].clear();
			for(int p=1;p<=m;p++){
				if(p==i||p==j) continue;
				e[u[p]].emplace_back(v[p],0);
				e[v[p]].emplace_back(u[p],0);
			}
			e[u[i]].emplace_back(v[i],1);
			e[v[i]].emplace_back(u[i],1);	
			e[u[j]].emplace_back(v[j],1);
			e[v[j]].emplace_back(u[j],1);			
			int sum=0;
			for(int p=1;p<=k;p++){
				sum+=dis(s[p],t[p]);
				if(clock()*1.0/CLOCKS_PER_SEC>3.9) break;
			}
			ans=max(ans,sum);
			if(clock()*1.0/CLOCKS_PER_SEC>3.9) break;
		}
		if(clock()*1.0/CLOCKS_PER_SEC>3.9) break;
	}
	cout<<ans<<"\n";
	return 0;
}